public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;
        //构造方法
        public TreeNode(char val) {
            this.val = val;
        }
    }
    //以穷举法创建一个二叉树
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;

        return A;
    }
    //前序遍历
    public void perOrder(TreeNode root) {
        if(root == null) {
            return;//空数不返回
        }
        //直接打印每个根节点，本质是递归！！！
        System.out.print(root.val + " ");
        //通过递归找到左数根节点，当左节点为空结束递归返回
        perOrder(root.left);
        //通过递归找到右数根节点，当右节点为空结束递归返回
        perOrder(root.right);
    }
    //中序遍历
    public void inOrder(TreeNode root) {
        if(root == null) {
            return;//初始条件，结束条件
        }
        //左节点
        inOrder(root.left);
        //根节点
        System.out.print(root.val + " ");
        //右节点
        inOrder(root.right);
    }
    //后序遍历
    public void postOrder(TreeNode root) {
        if(root == null) {
            return;//初始条件，结束条件
        }
        //左节点
        inOrder(root.left);
        //右节点
        inOrder(root.right);
        //根节点
        System.out.print(root.val + " ");
    }
/*
    public TreeNode find1(TreeNode root,int val) {
        //为空
        if(root == null) {
            return null;
        }
        //结束条件
        if(root.val == val) {
            return root;
        }
        //递归 左子树递归
        find1(root.left,val);
        //右子树递归
        find1(root.right,val);
        //找不到
        return null;
    }
*/

    //获取节点个数
    public static int nodeSize;//进行递归，所以放在外面
    public void size1(TreeNode root) {//依次递归
        if(root == null) {//二叉树为空
            return ;
        }
        //不为空，遍历并节点个数++
        nodeSize++;
        size1(root.left);
        size1(root.right);
    }
    public int size2(TreeNode root) {//子问题法：左子数 + 右子树 + 1(根节点)
        //为空
        if(root == null) {
            return 0;
        }
        //左子树节点 + 右子树节点 + 根节点
        return size2(root.left) + size2(root.right) + 1;//画图理解，不断通过递归，不断递归得到左右子树最上面的值最后加上根节点即可
    }
    //获取叶子结点的个数
    public static int leafSize;
    public void getLeafNodeCount1(TreeNode root) {//遍历
        if(root == null) {
            return;
        }
        //左右子树为空，叶子结点++
        if(root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    public int getLeafNodeCount2(TreeNode root) {//子问题
        if(root == null) {
            return 0;
        }

        if(root.left == null && root.right == null) {
            return 1;
        }
        //左 + 右
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }
    //root的第k层有多少个节点
    public int getKLevelNodeCount(TreeNode root,int k) {
        //空树
        if(root == null) {
            return 0;
        }
        //k为1返回
        if(k == 1) {
            return 1;
        }
        //左子树 + 右子树
        return getKLevelNodeCount(root.left,k - 1) +  getKLevelNodeCount(root.right,k - 1);
    }
    //获取二叉树的高度
    public int getHeight(TreeNode root) {
        //空树
        if(root == null) {
            return 0;
        }
        //左树高度与右树高度最大值 + 1;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight,rightHeight) + 1;
    }
    //检测值为value的节点是否存在
    public TreeNode find(TreeNode root,int val) {
        //空树
        if(root == null) {
            return null;
        }
        //判断根节点
        if(root.val == val) {
            return root;
        }
        //递归判断左子树 右子树
        TreeNode leftVal = find(root.left,val);
        if(leftVal != null) {
            return leftVal;
        }
        //递归判断右子树
        TreeNode rightVal = find(root.right,val);
        if(rightVal != null) {
            return rightVal;
        }
        //如果左右子树均不存在value返回null
        return null;
    }
 }
